2.
2024
/
(C++ )
: 3 :75
: - ,
-
1. :
(a)
() -
2. ? '
15
-
3. ? ?
-
4. ?
-
2.
-
5.
-
6. :
-
7. 15
8. ? 15 -
2.
2024
/
(C++ )
: 3 :75
: - ,
-
1. :
(a)
() -
:
, ,
,
--
:
"
?" ,
?
:
" ?"
2.
: -
? - ?
"
?"
"
?"
,
,
:
• 10
• 10,00,000
, '
–
,
:
• O(1) – ( !)
• O(log n) – ()
• O(n) – ()
• O(n²) – ( )
• O(2ⁿ) – !
:
=
=
:
:
• ,
• ,
-
-
2.
-
:
•
•
• , , ,
:
" ?"
:
•
' ,
( )
•
' ,
, ,
– --
: -
?
•
•
,
- -
?
:
"
,
"
,
,
!
2.
1:
'
• ()
• (
)
,
,
- !
2:
?
,
,
3:
RAM ' ?
- -
?
:
•
•
•
•
•
•
2.
,
, :
✔
✔
✔
-
:
' :
• ()
• ()
– -
:
,
,
,
-
,
2.
,
2. ? '
:
-
,
, ,
( )
,
, '
: -
,
' :
1. : ( , , )
2. ( ) :
- :
{
int ; //
struct Node* ; //
};
•
• NULL ,
2.
( ),
,
• :
• : -
• : ,
,
'
'
:
1.
2.
3.
4. (C/C++ )
:
void deleteNode(struct Node** head, int position) {
//
(*head == NULL) ;
* = *;
//
( == 0) {
* = ->; //
(); //
;
}
//
(int i = 0; temp != NULL && i < - 1; i++) {
2.
= ->;
}
//
( == NULL || -> == NULL)
;
// ->
struct Node* = ->->;
(->); //
temp->next = ; //
}
:
→ [10 | ] → [20 | ] → [30 | ] → [40 | ] → NULL
:
• 10
• 20
• 30
• 40
: 2 ( 30 ) '
-- :
1. (10)
2. 2 → 20
3. 20 30 (, 40)
4. 30
:
→ [10 | ] → [20 | ] → [40 | ] → NULL
, 30
2.
,
( ) ,
,
• :
• /:
• :
• :
' nth
;
,
,
30
-
3. ? ?
-
: ?
,
,
:
LIFO - ,
:
2.
•
,
•
:
✔
✔
✔
✔
,
,
,
' TOP
?
:
,
'
TOP , :
• ?
• ?
• ?
, :
= -1
, TOP
, TOP
= 5
2.
0
1
2
3
4
:
= -1
10
:
= 0
20
:
= 1
…
: → 10 → 20 → 30 →
'
' 4
1. ()
PUSH ,
: ( )
, TOP3
TOP '
,
:
2.
:
[]
= -1
5 →
[5]
= 0
10 →
[5, 10]
= 1
20 →
[5, 10, 20]
= 2
20 '
2. POP ()
POP , TOP
: ( )TOP3 '
POP , :
:
:
[5, 10, 20]
= 2
2.
POP → 20
[5, 10]
= 1
POP → 10
[5]
= 0
POP → 5
[]
= -1
3. /
:
[5, 10, 20]
= 2
PEEK :
20
'
4. isEmpty() isFull()
()
TRUE :
== -1
2.
()
TRUE :
== - 1
-
:
1.
2.
3.
:
→ → → ()
BACK
:
• (POP)
•
•
'
LIFO
?
; ' :
✔
✔
✔ /
✔
✔
✔ ( )
2.
✔
✔ , (LIFO) '
✔TOP
✔
✔ :
• → '
• POP →
• →
• / →
✔
✔
,
,
,
, ,
'
4. ?
-
: - , ,
-
,
FIFO ( , ) ' -
,
'
2.
: ' ,
,
,
:
' ,
-
,
• FIFO
• :
o :
o :
• ' ,
'
1.
•
• , ,
• ' , - :
𝑟𝑒𝑎𝑟 = (𝑟𝑒𝑎𝑟 + 1)%𝑠𝑖𝑧𝑒
• , :
𝑓𝑟𝑜𝑛𝑡 = (𝑓𝑟𝑜𝑛𝑡 + 1)%𝑠𝑖𝑧𝑒
% ,
2.
•
• ,
•
'
2.
-- :
1. ()
•
• ,
• :
𝑟𝑒𝑎𝑟 = (𝑟𝑒𝑎𝑟 + 1)%𝑠𝑖𝑧𝑒
2. ()
•
• ,
• :
𝑓𝑟𝑜𝑛𝑡 = (𝑓𝑟𝑜𝑛𝑡 + 1)%𝑠𝑖𝑧𝑒
3. ( )
•
4.
•
• :
(𝑟𝑒𝑎𝑟 + 1)%𝑠𝑖𝑧𝑒 == 𝑓𝑟𝑜𝑛𝑡
5.
•
• :
𝑓𝑟𝑜𝑛𝑡 == −1
5
:
= -1, = -1
= [ , , , ]
2.
1: 10
= 0, = 0
= [10, , , , ]
2: 20
= 0, = 1
= [10, 20, , , ]
3: 30
= 0, = 2
= [10, 20, 30, , ]
4: (10
)
= 1, = 2
= [ , 20, 30, , ]
5: 40, 50, 60
• 40 50 :
= 1, = 4
= [, 20, 30, 40, 50]
• 60 : 0 -
= 1, = 0
= [60, 20, 30, 40, 50]
0 '
2.
,
,
•
•
•
•
•
,
- , , , ,
-
-
5.
-
?
-
?
!
,
'
,
,
' :
2.
:
( )
- --
:
5, 9, 12, 18, 23, 30, 45, 50
23
1:
,
18
18 23 ?
:
23 18 18 ?
23 ,
,
:
23, 30, 45, 50
2:
30
30 23 ?
23 30 ? !
2.
:
23
3:
23 ? !
- !
:
1.
2.
3. ',
4.
( )
1.
2.
3.
4. → !
5. →
6. →
7.
2.
: ,
1,000 ,
1,000
:
1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1
1000 , 10
, ?
:
O(log₂ n)
:
• 1,000 → 10
• 1,000,000 → 20
:
(1)
( , O(log n) )
,
:
1.
- '
,
,
2.
2. '
'
'
:
•
•
'
3.
, ,
(, , )
4.
,
5.
( ),
?
-
:
•
•
•
•
•
•
2.
•
" "
, - O(log n)
,
, '
, ,
6. :
: - , ,
-
, ,
,
,
: ' -
?
-
( , ) -
• : —
• :- - -
• :
2.
" "
',
--
1.
2.
3.
4. '
5.
:
i = 0 n-1 :
-_ = i
j = i+1 n :
arr[j] < arr[-_ ]:
-_ = j
(arr[i], arr[-_ ])
-
:
[64, 25, 12, 22, 11]
Selection Sort
1:
• : [64, 25, 12, 22, 11]
• 11
• 11 64
• : [11, 25, 12, 22, 64]
2:
• : [11, 25, 12, 22, 64]
• [25, 12, 22, 64] 12
• 12 25
• : [11, 12, 25, 22, 64]
3:
2.
• : [11, 12, 25, 22, 64]
• [25, 22, 64] 22
• 22 25
• : [11, 12, 22, 25, 64]
4:
• : [11, 12, 22, 25, 64]
• [25, 64] 25
• 25 (
)
• : [11, 12, 22, 25, 64]
5:
• (64),
:
[11, 12, 22, 25, 64]
, ,
, , '
1. :
o :𝑂(𝑛
2
)
o :𝑂(𝑛
2
)
o :𝑂(𝑛
2
)
- -
2. :
o 𝑂(1)(- ,
)
3. :
o
( )
4. :
o
2.
•
•
• -
• 𝑂(𝑛
2
)
•
,
[29, 10, 14, 37, 13]
• 1: 10 29 → [10, 29, 14, 37, 13]
• 2: [29, 14, 37, 13] 13 29 → [10, 13, 14, 37,
29]
• 3: [14, 37, 29] 14 → [10, 13, 14, 37, 29]
• 4: [37, 29] 29 37 → [10, 13, 14, 29, 37]
• 5:
: [10, 13, 14, 29, 37]
-
,
-
7.
: ?
,
:
2 - -
,
2.
:
-
?
:
•
→
•
→
•
- → -
... ' -
- :
()
()
()
:
()
()
()
, ,
•
•
• (/ /)
•
• '
2.
C++
-
# <iostream>
std ;
{
:
//
( , ) {
a + b ;
}
//
( , , ) {
a + b + c;
}
//
( , ) {
a + b ;
}
};
() {
c;
cout << "2 : " << c.add(10, 20) << endl;
cout << "3 : " << c.add(10, 20, 30) << endl;
cout << "2 : " << c.add(5.5f, 4.5f) << endl;
0;
}
?
add()
:
• add() → 2
• add() → 3
2.
• () → 2
,
:
:
c.add(10, 20);
:
(, )
:
c.add(10, 20, 30);
:
(, , )
:
c.add(5.5f, 4.5f);
:
(, )
-
-
-
:
{
:
(
) {
cout << " : " << ;
}
2.
( ) {
cout << " : " << ;
}
(
, ) {
cout << " : " << ;
cout << " : " << ;
}
};
, display() :
•
•
•
, -
' :
✔
✔
✔
✔
✔
✔-
:
•
•
•
• ( , )
:
(){
2.
10;
}
() {
10.5;
}
— " ?"
:
( )
• -
• -
• ,
' -
•
•
-
-
,
8. ?
-
:-
- (OOP) ,
, ,
,
,
2.
: '
,
?
OOP (
) ( )
• ():
• (-):
"" ,
,
""
, ""
( -
)
1. :
2. - : ,
3. :
4. -:
' ,
-
• -
• ,
( )
, ,
2.
()
:
# 1
:
def ():
(" : ")
# 2
:
def ():
(" : ")
#
(, ):
():
(" : ")
#
c = ()
c.skill() # ?
. ()
:
:
:
() , (MRO)
- ()
:
/ \
..
2.
\ /
• D, B C
• B C A
• D A , B
C
- :
• ++:
• : (MRO)
1. :
2. : -
3. : -
1. :
2. :
3. - :
" "
,
C++
# <iostream>
std ;
{
:
() {
cout << " : " << endl;
}
};
2.
{
:
() {
cout << " : " << endl;
}
};
: , {
:
() {
cout << " : " << endl;
}
};
() {
c;
c.Father::skill(); //
c. ::();
. ();
0;
}
:
:
:
:
C++ ,
' - ,
- ,
,
,
- - ,
"
,
"
